import random
import copy
try:
	import sudoku
except:
	from . import sudoku
valid_values = sudoku.valid_values
Sudoku = sudoku.Sudoku

d_ = [
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
]

def random_solution(d=None):
	if d is None:
		d = copy.deepcopy(d_)
	def fill(i,j):
		if (i==9) and (j==0):
			return True
		valid = valid_values(d,i,j)
		if len(valid)>0:
			random.shuffle(valid)
			for v in valid:
				d[i][j] = v
				i2,j2 = (i+1,0) if j==8 else (i,j+1)
				if fill(i2,j2):
					return True
		d[i][j] = 0
		return False
	assert fill(0,0)
	return d
	
def random_sukodu(d_=None, max_difficulty=1000):
	d = d_ if d_ is not None else random_solution()
	# Sudoku.print(d)
	ss = []
	for i in range(9):
		for j in range(9):
			if d[i][j]==0: continue
			d2 = copy.deepcopy(d)
			d2[i][j] = 0
			solutions = Sudoku.search(copy.deepcopy(d2))
			if len(solutions)!=1: continue
			h,_ = solutions[0]
			ss.append([h,d2])
	if len(ss)==0:
		return []
	ss.sort(key=lambda x: len(x[0]))
	ss = [[h,d] for h,d in ss if len(h)==len(ss[0][0])]
	if d_ is None:
		ss = ss[-1:]
	random.shuffle(ss)
	for h,d in ss:
		if len(h)>max_difficulty:
			# print()
			return [[h,d]]
		# print(len(h), end=' ')
		res = random_sukodu(copy.deepcopy(d), max_difficulty)
		if len(res)==0:
			continue
		h2 = res[0][0]
		assert len(h2)>=len(h)
		if len(h)==len(h2):
			return res
		return [[h,d]]+res
	return [[h,d]]

def print_res(res):
	for h,d in res:
		print(f'\n#数字={sum([1 for i in range(9) for j in range(9) if d[i][j]>0])} 难度={len(h)}')
		print('设定',', '.join([f'位置{(i,j)}是{v}' for i,j,v in h]))
		Sudoku.print(d)

# res = random_sukodu(max_difficulty=1)
# print_res(res)
